1. Field of the Invention
This invention relates to data communications and in particular to an efficient reduced state maximum likelihood sequence estimator for use in data communication systems.
2. Description of the Related Art
The received signal in a digital communication system includes noise and distortion caused at least in part by intersysmbol interference (ISI). One such digital communication system employs modems, which use digital modulation techniques to modulate and demodulate binary data over analog band-limited communications channels, e.g., telephone lines.
Modems typically conform to international standards to ensure interoperability with modems from other manufacturers. One such standard is the V.34 specification described in ITU-T Recommendation V.34, A Modem Operating at Data Signalling Rates of up to 28 800 bits/s for Use on the General Switched Telephone Network and on Leased Point-to-Point 2-Wire Telephone-Type Circuits, dated September, 1994 (previously CCITT Recommendation V.34), which is hereby incorporated herein, in its entirety, by reference. Another such standard is the V.90 specification described in ITU-T Recommendation V.90, A Digital Modem and Analogue Modem Pair For Use on the Public Switched Telephone Network (PSTN) At Data Signalling Rates of Up To 56 000 bits/s Downstream and Up To 33 600 bits/s Upstream, dated September, 1998, which is hereby incorporated herein, in its entirety, by reference.
Maximum Likelihood Sequence Estimators (MLSE) are widely used in data communications such as modem communications for decoding data passed through the channels with intersymbol interference (ISI) and for decoding convolutionally encoded data. The Viterbi algorithm (VA) is quite often used to implement MLSE. A brief description of the Viterbi algorithm, which is well known in the art, is provided to facilitate an understanding of the present invention.
Assume that a sequence of symbols x={xi}, i xcex5]xe2x88x92xe2x88x9d;xe2x88x9d[, xixcex5A={a1, a2, . . . aL} is transmitted through a channel with impulse response h={hi}, such that hixe2x89xa00 only when 0 less than hi less than =M, where Mxe2x88x921 is the number of history terms contained in the channel. The signal received at the other end of the channel in the absence of noise is defined as y=x*h, where xe2x80x9c*xe2x80x9d denotes a convolution. If the noise xcex7 is added to the signal in the channel, then the signal at the other end of the channel contains that noise and is defined as z=y+xcex7. The receiver must reconstruct the transmitted sequence of symbols x, based on the received sequence z. At the time nT the following can be used to reconstruct the most recently sent symbol xn:
xn=(ynxe2x88x92(xnxe2x88x921h1+. . . +xnxe2x88x92M+1 hMxe2x88x921))/hoxe2x80x83xe2x80x83(1)
From the equation (1) it can be seen that besides the received signal yn, value xn depends on the vector {xnxe2x88x921, . . . xnxe2x88x92M+1} of Mxe2x88x921 previously decoded symbols. That vector will be further referred to herein as a state. With each new decoded symbol, the state of the decoder changes to reflect the new value of the vector {xnxe2x88x921, . . . xnxe2x88x92M+1}. That is, if at a time nT the state was {xnxe2x88x921, . . . xnxe2x88x92M+1} then at a time (n+1)T the new state will be {xn, . . . xnxe2x88x92M+2} and so forth. That change will be further referred herein as a state transition. The history of state transitions represents a state trajectory. Since each symbol xn belongs to a finite alphabet A of size L, there can only be K=LMxe2x88x921 unique states. All states comprise a state set S={s1, s2, . . . sk}, where each element Sk is a vector of Mxe2x88x921 elements that belong to alphabet A such that skxe2x89xa0sm for kxe2x89xa0m.
Since the noiseless channel output yn is not available to the receiver, the value of xn cannot be determined with absolute certainty, and instead an estimate is used:
xn=(znxe2x88x92(xnxe2x88x921h1+. . . +xnxe2x88x92M+1 hMxe2x88x921))/hoxe2x80x83xe2x80x83(2)
The Euclidean distance, tn1, from the alphabet element a1 to the estimate xn, is defined as tn1xe2x88x92(xnxe2x88x92a1)2, which provides the measure of likelihood that the transmitted symbol xn equals a1 at the time nT.
In a simple receiver, the alphabet element with the minimum Euclidean distance is selected and xn is assumed to be equal to that alphabet element. However if xn is not determined correctly (e.g. due to noise), that incorrect value will cause incorrect state transition causing future symbols to be decoded incorrectly affecting in turn future state transitions and so on. That condition is called xe2x80x9cerror propagation.xe2x80x9d
To avoid the xe2x80x9cerror propagationxe2x80x9d problem, all possible decoder states and all possible state transitions must be examined. A state metric Dn={dn1, dn2, . . . , dnK} defines the measure of likelihood, such that each element dnk defines the measure of likelihood of state sk at a time nT which is directly related to the Euclidean distance of the elements of the symbol vector corresponding to state sk. The relationship of the state metric D and state set S is shown in FIG. 1 in which set S is shown to consist of four states s1 through s4. In the example shown in FIG. 1 Axcex5(0,1) and L=2 and M=3. Each state s1 through s4 has an associated state metric d1 through d4 in D.
1. For each state sk of a set S calculate a symbol estimate xnk, based on received symbol zn according to equation (2) above.
2. For each state sk of a set S consider L transitions from that state, and for each transition combination (k, 1) calculate a combined metric dk1=dk+tk1, where tk1 is an Euclidean distance of the alphabet element a1 from the symbol estimate xnk, tk1=(xnkxe2x88x92a1)2.
3. For each state sk of a set S consider L transitions to that state, selecting the one with the minimum combined metric d calculated during step 2 and assign its value to the state metric dk.
4. Find the state with the minimum metric dk storing a transition that led to that state as a candidate optimal trajectory.
5. The first four steps are repeated for each value of n, i.e., for each received symbol.
The optimal trajectory for the state with the smallest metric is considered the optimal path (most likely sequence) at a given time. As it can be seen from the above description, the computational complexity of the Viterbi algorithm is proportional to LM. For high speed communication systems over band limited channels the value of L is large, thus making the Viterbi algorithm complexity potentially prohibitive even for channels with relatively short impulse response.
One use of the Viterbi algorithm, as stated above, is in modem data transmission. Such transmission is always affected by linear intersymbol interference (ISI) and by noise. These two impairments are typically countered by equalization, a technique which minimizes ISI and noise at periodic instances at which decisions are taken. The ultimate goal of the equalizer is to minimize a combined effect of ISI and noise and thus reduce the probability of incorrect decisions. Traditionally, dial up modem designers used Linear Equalizers (LE) to do the job. The performance of LE is quite satisfactory when the combination of the channel impulse response and the equalizer can form a Nyquist-1 pulse to satisfy the distortionless (zero ISI) criterion. To achieve that goal, the bandwidth of the channel has to be wider than the symbol rate employed by the modem.
The new generation of modems conforming to the V.90 recommendation no longer satisfy this criterion. The impulse response of a PCM codec is designed to achieve satisfactory transmission of voice signals, and its bandwidth is always more narrow than the 8000 Hz symbol rate used by a modem conforming to the V.90 standard. The spectral nulls at DC and 4000 Hz generate infinite noise enhancements when LE is employed. To reduce such noise enhancements, more advanced equalization techniques should be used. Those are decision feedback equalizers (DFE) and partial response equalizers (PRE). Although usually treated separately, LE and PRE are just special cases of DFE. DFE includes two portions: the forward equalizer (FE) and the feedback equalizer (FBE). Both the FE and the FBE can be implemented as linear FIR filters, where the input samples serve as an input to the FE and the previously decoded symbols serve as input to the FBE. The output of both the FE and the FBE are added together and the result is used as the basis for decision for determining the transmitted signal. DFE allows some ISI to remain at the output of FE to be then canceled by FBE. It has been shown that DFE can be the optimum receiver with no decision delay. When, used in conjunction with Viterbi detector, (VD) DFE becomes a powerful tool in battling ISI even for channels with spectral nulls.
However the implementation of a Viterbi detector grows considerably more complex with number of levels used by the transmission symbols and by number of taps in the FBE. The computational complexity of a Viterbi detector is proportional to LM where M is the number of FBE taps and L is the size of the transmitted symbols alphabet.
Partial response equalizers (PRE), being a special case of DFE are used to reduce the computational complexity of the Viterbi detector by forcing the FE to leave uncanceled only a controlled amount of ISI, thus requiring only a small number of FBE taps to cancel it. The combination of channel impulse response and FE of PRE form a response, called Partial Response (PR), which contains only a few, usually integer-valued coefficients, thus allowing controlled levels of ISI from a small number of symbols to be present at the instances of decision making. A Viterbi detector is then employed to remove that ISI and make the most probable decision. The choice of partial response depends heavily on the transmission channel. When spectral characteristics of the partial response match those of a channel, the FE has an easier task and noise enhancement is limited. For a channel with spectral nulls, it is highly desirable to use a partial response having spectral nulls at the same positions to avoid infinite noise enhancement. A pulse code modulation (PCM) channel has two spectral nulls: one around DC, another around 4000 Hz, thus confining the choice of the partial response for PCM modem to those with the same spectral nulls. Class IV Partial Response (PRIV) often called modified duobinary, has long been used for the channels with similar characteristics and is well known in the art.
The PRIV FE output contains the difference of two symbols spaced by two symbol intervals:
yn=xnxe2x88x92xnxe2x88x922
Since ISI from only one symbol is present, the number of states of the Viterbi detector equals Lxe2x80x94the size of the symbol alphabet. For data rates achievable by a V.90 compliant modem, L less than =128. Although implementation of 128-state Viterbi decoder is not trivial, Set Partitioning, a well known technique in the art, can be used to reduce the number of Viterbi detector states to a more manageable number. However, when the channel has severe attenuation at a wider range of frequencies adjacent to DC and 4000 Hz, the noise enhancement by a class IV partial response equalizer becomes intolerable.
Therefore, it would be desirable to utilize a partial response equalizer that does not exhibit intolerable noise enhancement and to have the performance of a Viterbi decoder with manageable complexity.
Accordingly the invention provides a reduced state maximum likelihood sequence estimator that causes only a slight degradation of performance relative to an implementation of a full state Viterbi decoder. That allows the use of improved equalization techniques that greatly improve performance for channels with severe attenuation and spectral nulls.
In one embodiment of the invention, a method is provided for implementing a reduced state maximum likelihood sequence estimator in a communications system to decode a received signal. The method includes retaining kn states of a total number of K states, kn less than K, each retained state having an associated state metric. (J)(kn) new states are determined based on kn previous states and a most recently received symbol, using J transitions, J being a less than L, where L is a size of a symbol alphabet. (J)(kn) new state metrics are determined which are respectively associated with each new state. The new state metrics are compared to a threshold and those states whose metric does not exceed the threshold are retained.
In another embodiment, the invention provides a modem that includes a partial response class V (PRV) equalizer coupled in its receive path. In still another embodiment of the invention a modem includes a reduced state maximum likelihood sequence estimator (MLSE) in its receive path. That MLSE may be coupled to a partial response equalizer. The reduced state maximum likelihood sequence estimator retains a varying number of reduced states. The number of retained states may be limited by use of an adaptive threshold that limits the number of retained states between a lower bound and an upper bound. The threshold may be determined according to a metric of a most likely state of the retained states and a selected one of a plurality of associated transition metrics.